package com.pan.alg.niuke.link;

import java.util.ArrayList;
import java.util.List;

/**
 * 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
 * 例如：
 * 给出的链表为1 \to 2\to 3\to 3\to 4\to 4\to51→2→3→3→4→4→5, 返回1\to 2\to51→2→5.
 * 给出的链表为1\to1 \to 1\to 2 \to 31→1→1→2→3, 返回2\to 32→3.
 *
 * 数据范围：链表长度 0 \le n \le 100000≤n≤10000，链表中的值满足 |val| \le 1000∣val∣≤1000
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 * 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 */
public class LinkDeleteDuplicates2 {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        //1、find head
        if(head==null||head.next==null){
            return head;
        }

        List<ListNode> listNodes = new ArrayList<>();
        ListNode pre = head;
        ListNode current = head.next;
        if(pre.val!=current.val){
            listNodes.add(pre);
        }
        while(current!=null){
            if(pre.val==current.val){
                pre=current;
                current=current.next;
            }else{
                if(current.next==null||current.next.val!=current.val){
                    listNodes.add(current);
                }
                pre=current;
                current=current.next;
            }
        }

        return ListNodeUtil.transListNode2LinkNode(listNodes);

    }
}
